package com.monkeyboy.list;

import com.monkeyboy.ListNode;

/**
 * 一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。
 *
 * 解题思路：
 *  1. 先判断是不是循环链表，通过一个二倍快指针一个慢指针，这样快指针总会追上慢指针
 *  2. 然后根据第一步相等时候开始循环一个指针计算出环状节点的个数
 *  3. 开始找入口节点，从链表头开始走，由于一个环走一圈会回到原点，所以如果没有回到原点的话剩下的节点就是入口之前的非环状节点
 *      。而非环状节点到入口节点的数量就等于没有走完的那圈距离
 *
 *  这种题目就需要考虑到环的特点，环路走一圈应该回到原点，如果没有回到原点说明就浪费在其它地方去了
 *  所以应该先计算出环节点的个数
 * @Author Gavin
 * @date 2021.04.03 11:06
 */
public class List05 {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null){
            return null;
        }
        // 1.判断链表中有环
        ListNode l=pHead,r=pHead;
        boolean flag = false;
        while(r != null && r.next!=null){
            l=l.next;
            r=r.next.next;
            if(l==r){
                flag=true;
                break;
            }
        }
        if(!flag){
            return null;
        }else{
            // 2.得到环中节点的数目
            int n=1;
            r=r.next;
            while(l!=r){
                r=r.next;
                n++;
            }
            // 3.找到环中的入口节点
            /**
             * 先让一个节点从头走完一圈环状的距离，剩下的距离到入口节点的个数就等于另一个节点从头
             * 开始到环状入口的距离
             */
            l=r=pHead;
            for(int i=0;i<n;i++){
                r=r.next;
            }
            while(l!=r){
                l=l.next;
                r=r.next;
            }
            return l;
        }

    }
    public ListNode EntryNodeOfLoop2(ListNode pHead) {//第二种，思路和上面一样，代码更简洁
        if (pHead == null || pHead.next == null)
            return null;
        ListNode slow = pHead, fast = pHead;
        do {
            fast = fast.next.next;
            slow = slow.next;
        } while (slow != fast);
        fast = pHead;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    public static void main(String[] args) {

    }
}
